//
// Created by wenyaxi on 24-10-28.
//
#include <common.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        for(int first=0;first<nums.size()-2;first++) {
            if(first>0 && nums[first]==nums[first-1]) {
                continue;
            }
            int target = -nums[first];
            if(target<0)break;
            int third=nums.size()-1;
            for(int second=first+1;second<nums.size()-1;second++) {
                if(second>first+1 && nums[second]==nums[second-1]) {
                    continue;
                }
                while(third>second && nums[third]+nums[second]>target) {
                    third--;
                }
                if(second>=third) break;
                if(nums[third]+nums[second]==target) {
                    ans.push_back({nums[first],nums[second],nums[third]});
                }
            }
        }
        return ans;
    }
};

int main(int argc, char *argv[]) {
    //[-1,0,1,2,-1,-4]
    //[0,1,1]
    //[0, 0, 0]
    vector<int> nums = {-1,0,1,2,-1,-4};
    auto x = Solution().threeSum(nums);
    for(auto row: x) {
        for(auto val: row) {
            cout<<val<<" ";
        }
        cout<<endl;
    }
    return 0;
}
